

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-08
 * Time: 10:13
 */

//二叉搜索树与双向链表
public class Test {

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }

        ConvertChild(pRootOfTree);

        //找头节点
        TreeNode head = pRootOfTree;
        while (head.left != null) {
            head = head.left;
        }

        return head;
    }

    //prev是用来记录'每次'要修改节点的前一个节点
    TreeNode prev = null;

    public void ConvertChild(TreeNode root) {
        //中序遍历
        if (root == null) {
            return;
        }

        //左
        ConvertChild(root.left);

        //根
        root.left = prev;
        //在树第一次来到最左边，prev是空
        if (prev != null) {
            prev.right = root;

        }

        //每个节点的左右节点改了，才可以‘每次’的走
        prev = root;

        //右
        ConvertChild(root.right);

    }
}
